{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bracket LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: generateParenthesis"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #括号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。</p>\n",
    "\n",
    "<p>说明：解集不能包含重复的子集。</p>\n",
    "\n",
    "<p>例如，给出 n = 3，生成结果为：</p>\n",
    "\n",
    "<pre>\n",
    "[\n",
    "  \"((()))\",\n",
    "  \"(()())\",\n",
    "  \"(())()\",\n",
    "  \"()(())\",\n",
    "  \"()()()\"\n",
    "]\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bracket-lcci](https://leetcode.cn/problems/bracket-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bracket-lcci](https://leetcode.cn/problems/bracket-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = n * 2\n",
    "        ans = []\n",
    "        path = [''] * m\n",
    "        def dfs(i: int, open: int) -> None:\n",
    "            if i == m:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            if open < n:  # 可以填左括号\n",
    "                path[i] = '('\n",
    "                dfs(i + 1, open + 1)\n",
    "            if i - open < open:  # 可以填右括号\n",
    "                path[i] = ')'\n",
    "                dfs(i + 1, open)\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n <= 0: return []\n",
    "        res = []\n",
    "\n",
    "        def dfs(paths, left, right):\n",
    "            if left > n or right > left: return\n",
    "            if len(paths) == n * 2:  # 因为括号都是成对出现的\n",
    "                res.append(paths)\n",
    "                return\n",
    "\n",
    "            dfs(paths + '(', left + 1, right)  # 生成一个就加一个\n",
    "            dfs(paths + ')', left, right + 1)\n",
    "\n",
    "        dfs('', 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "\n",
    "        def dfs(left, right, res):\n",
    "            if len(res) == 2 * n:\n",
    "                ans.append(res)\n",
    "                return\n",
    "            if left < n:\n",
    "                dfs(left + 1, right, res + '(')\n",
    "            if right < left:\n",
    "                dfs(left, right + 1, res + ')')\n",
    "\n",
    "        dfs(0, 0, '')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        cur = []\n",
    "        def dfs(l, r, cur):\n",
    "            if r == 0:\n",
    "                res.append(\"\".join(map(str, cur)))\n",
    "                return\n",
    "            if l > 0:\n",
    "                cur.append('(')\n",
    "                dfs(l - 1, r, cur)\n",
    "                cur.pop()\n",
    "            if r > 0 and r > l:\n",
    "                cur.append(')')\n",
    "                dfs(l, r - 1, cur)\n",
    "                cur.pop()\n",
    "        dfs(n, n, cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        re = []\n",
    "        state = ''\n",
    "\n",
    "        def dsp(state, p, q):       #p,q分别表示(和)还剩的个数，有个隐含条件：就是(在组合时候比)用的多或相等\n",
    "            if p > q:               #非法，剪枝\n",
    "                return \n",
    "            if q == 0:              #)用完之时\n",
    "                re.append(state)\n",
    "            \n",
    "            if p > 0:\n",
    "                dsp(state+'(', p-1, q)\n",
    "            if q > 0:\n",
    "                dsp(state+')', p, q-1)\n",
    "\n",
    "        dsp(state, n, n)\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans, path = [], []\n",
    "        def dfs(l, r):\n",
    "            if l == 0 and r == 0:\n",
    "                ans.append(\"\".join(path[:]))\n",
    "                return\n",
    "            if r >= l:\n",
    "                if l > 0:\n",
    "                    path.append('(')\n",
    "                    dfs(l - 1, r)\n",
    "                    path.pop()\n",
    "                if r > 0:\n",
    "                    path.append(')')\n",
    "                    dfs(l, r - 1)\n",
    "                    path.pop()\n",
    "        dfs(n, n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def dfs(path: list[str], left_paren: int = 0, right_paren: int = 0, balance: int = 0):\n",
    "            # balance = ( - )\n",
    "            if balance < 0:\n",
    "                return\n",
    "            if len(path) == n * 2:\n",
    "                if balance == 0:\n",
    "                    ans.append(\"\".join(path))\n",
    "                return\n",
    "\n",
    "            if left_paren > 0:\n",
    "                path.append(\"(\")\n",
    "                dfs(path, left_paren - 1, right_paren, balance + 1)\n",
    "                path.pop()\n",
    "            if right_paren > 0:\n",
    "                path.append(\")\")\n",
    "                dfs(path, left_paren, right_paren - 1, balance - 1)\n",
    "                path.pop()\n",
    "            \n",
    "            return\n",
    "    \n",
    "        ans = []\n",
    "        dfs([], n, n, 0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        res=[]\n",
    "        def backtrack(left,right,path):#分别代表左括号和又括号的数目\n",
    "            if len(path)==2*n:\n",
    "                res.append(''.join(path))\n",
    "                return \n",
    "            if left<n:\n",
    "                path.append('(')\n",
    "                backtrack(left+1,right,path)\n",
    "                path.pop()\n",
    "            if right<left:\n",
    "                path.append(')')\n",
    "                backtrack(left,right+1,path)\n",
    "                path.pop()\n",
    "        backtrack(0,0,[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def func(s,a,b):\n",
    "            if(a==0 and b==0):\n",
    "                ansarr.append(s)\n",
    "                return\n",
    "            if(a!=0):\n",
    "                func(s+\"(\",a-1,b+1)\n",
    "            if(b!=0):\n",
    "                func(s+\")\",a,b-1)\n",
    "            return\n",
    "        ansarr = []\n",
    "        func(\"\",n,0)\n",
    "        return ansarr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(i, j, s):\n",
    "            if i<j or i+j>2*n:\n",
    "                return \n",
    "            if i==n and j==n:\n",
    "                ans.append(s)\n",
    "                return \n",
    "            if i==j:\n",
    "                dfs(i+1, j, s+'(')\n",
    "            else:\n",
    "                dfs(i+1, j, s+'(')\n",
    "                dfs(i, j+1, s+')')\n",
    "        dfs(0, 0, '')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        lNum = n\n",
    "        rNum = n\n",
    "        res = []\n",
    "        path = []\n",
    "        def dfs():\n",
    "            nonlocal lNum, rNum\n",
    "            if len(path) == 2*n:\n",
    "                res.append(''.join(path))\n",
    "            if lNum > 0:\n",
    "                path.append('(')\n",
    "                lNum -= 1\n",
    "                dfs()\n",
    "                lNum += 1\n",
    "                path.pop()\n",
    "            if rNum > lNum:\n",
    "                path.append(')')\n",
    "                rNum -= 1\n",
    "                dfs()\n",
    "                rNum += 1\n",
    "                path.pop()\n",
    "        dfs()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        result = []\n",
    "        def dfs(left,right,path):\n",
    "            if left == right == 0:\n",
    "                result.append(path)\n",
    "            if left < right:\n",
    "                dfs(left,right-1,path+\")\")\n",
    "            if left > 0:\n",
    "                dfs(left-1,right,path+\"(\")\n",
    "        dfs(n,n,\"\")\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        s_list = ['(',')'] * n\n",
    "        res = []\n",
    "        def pailie(index):\n",
    "            if index == len(s_list):\n",
    "                res.append(''.join(s_list))\n",
    "                return\n",
    "            dict_norepeat = []\n",
    "            for i in range(index, len(s_list)):\n",
    "                if s_list[i] in dict_norepeat:\n",
    "                    continue\n",
    "                dict_norepeat.append(s_list[i])\n",
    "                s_list[i], s_list[index] = s_list[index], s_list[i]\n",
    "                pailie(index + 1)\n",
    "                s_list[i], s_list[index] = s_list[index], s_list[i]\n",
    "        pailie(0)\n",
    "        res_tmp = []\n",
    "        for i in res:\n",
    "            stack = []\n",
    "            for j in i:\n",
    "                if len(stack) > 0 and j == ')' and stack[-1] == '(':\n",
    "                    stack.pop()\n",
    "                else:\n",
    "                    stack.append(j)\n",
    "            if not stack:\n",
    "                res_tmp.append(i)\n",
    "\n",
    "        return res_tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "\n",
    "        def dfs(l, r, path):\n",
    "            if l == r == n:\n",
    "                ans.append(path)\n",
    "                return\n",
    "            \n",
    "            if l < n:\n",
    "                dfs(l+1, r, path + \"(\")\n",
    "            \n",
    "            if r < l:\n",
    "                dfs(l, r+1, path + \")\")\n",
    "\n",
    "        dfs(0, 0, \"\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        self.ans = []\n",
    "        def tb(s,l,r):\n",
    "            if len(s) == 2*n: self.ans.append(s)\n",
    "            if l < n: tb(s+'(',l+1,r)\n",
    "            if r<l: tb(s+')',l,r+1)\n",
    "        tb('',0,0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        \n",
    "        def myway(leftnum,rightnum,now):\n",
    "            if leftnum==0 and rightnum==0:\n",
    "                outlist.append(\"\".join(now))\n",
    "\n",
    "            if leftnum:\n",
    "                now.append(\"(\")\n",
    "                leftnum-=1\n",
    "                myway(leftnum,rightnum,now)\n",
    "                leftnum+=1\n",
    "                now.pop()\n",
    "\n",
    "            if leftnum<rightnum and rightnum:\n",
    "                now.append(\")\")\n",
    "                rightnum-=1\n",
    "                myway(leftnum,rightnum,now)\n",
    "                rightnum+=1\n",
    "                now.pop()\n",
    "\n",
    "        outlist=[]\n",
    "        myway(n,n,[])\n",
    "        return outlist\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtrack(self,res,ans,left,right,n):\n",
    "        if len(ans)==2*n:\n",
    "            res.append(\"\".join(ans[:]))\n",
    "        if right<left:\n",
    "            ans.append(')')\n",
    "            self.backtrack(res,ans,left,right+1,n)\n",
    "            ans.pop()\n",
    "\n",
    "        if left>=right and left<n:\n",
    "            ans.append('(')\n",
    "            self.backtrack(res,ans,left+1,right,n)\n",
    "            ans.pop()\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        #前括号，后括号\n",
    "        res=[]\n",
    "        ans=[]\n",
    "        self.backtrack(res,ans,0,0,n)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def dfs(path, res, score):\n",
    "            if score>n:return\n",
    "            if len(path)>=2*n:\n",
    "                if len(path)==2*n and score==0:\n",
    "                    res.append(path)\n",
    "                return\n",
    "            for c in '()':\n",
    "                if c==')' and score==0:\n",
    "                    continue\n",
    "                dfs(path+c,res,score+1 if c=='(' else score-1)\n",
    "        res = []\n",
    "        dfs('',res,0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "\n",
    "        res = list()\n",
    "        path = ''\n",
    "\n",
    "        def IsRight(str):\n",
    "            tmp = []\n",
    "            for ch in str:\n",
    "                if ch == '(':\n",
    "                    tmp.append(ch)\n",
    "                else:\n",
    "                    if tmp == []:\n",
    "                        return False\n",
    "                    tmp.pop()\n",
    "            if tmp == []:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        def backtracking(index, path, right, left):\n",
    "            if index == 2*n:\n",
    "                if IsRight(path):\n",
    "                    res.append(path)\n",
    "            \n",
    "            if left < n:\n",
    "                backtracking(index+1, path+'(', right, left+1)\n",
    "            if right < n:\n",
    "                backtracking(index+1, path+')', right+1, left)\n",
    "        \n",
    "        backtracking(0, path, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ret = []\n",
    "        def dfs(l, r, s):\n",
    "            if l == n and r == n:\n",
    "                ret.append(s)\n",
    "            # if l > n or r > n:\n",
    "                # return\n",
    "            if l > r:\n",
    "                dfs(l, r+1, s + ')')\n",
    "            if l <= n:\n",
    "                dfs(l+1, r, s +'(')\n",
    "\n",
    "        dfs(1, 0, '(')\n",
    "        return ret\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        # print(self.isValid('()()'))\n",
    "        def backtracing(comb, res, ) -> None:\n",
    "            if len(comb) == n * 2:\n",
    "                if self.isValid(comb) == True:\n",
    "                    res.append(''.join(comb))\n",
    "                return \n",
    "            \n",
    "            for b in [')', '(']:\n",
    "                comb.append(b)\n",
    "                backtracing(comb, res)\n",
    "                comb.pop()\n",
    "\n",
    "        res = []\n",
    "        backtracing([], res)\n",
    "        return res \n",
    "    \n",
    "    def isValid(self, string: str) -> bool:\n",
    "        stack = []\n",
    "        for s in string:\n",
    "            if s == '(':\n",
    "                stack.append(')')\n",
    "            elif s == ')':\n",
    "                if stack:\n",
    "                    if s == stack[-1]:\n",
    "                        stack.pop()\n",
    "                else:\n",
    "                    return False \n",
    "        \n",
    "        if stack:\n",
    "            return False\n",
    "        else:\n",
    "            return True \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        def dfs(leftn, rightn, s):\n",
    "            if leftn == 0:\n",
    "                ans.append(s + \")\" * rightn)\n",
    "                return\n",
    "            if leftn == rightn:\n",
    "                dfs(leftn - 1, rightn, s + \"(\")\n",
    "            elif leftn < rightn:\n",
    "                dfs(leftn - 1, rightn, s + \"(\")\n",
    "                dfs(leftn, rightn - 1, s + \")\")\n",
    "        dfs(n,n,'')\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = 2 * n\n",
    "        ans, path = [], ['' for _ in range(m)]\n",
    "\n",
    "        def dfs(i, open):\n",
    "            if i == m:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            if open < n:\n",
    "                path[i] = '('\n",
    "                dfs(i + 1, open + 1)\n",
    "            if i - open < open:\n",
    "                path[i] = ')'\n",
    "                dfs(i + 1, open)\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "\n",
    "        output = []\n",
    "\n",
    "        def dfs(comb, current_left_bracket, current_right_bracket, n):\n",
    "            if current_right_bracket == n:\n",
    "                output.append(comb)\n",
    "                return\n",
    "            \n",
    "            if current_left_bracket < n:\n",
    "                dfs(comb + '(', current_left_bracket + 1, current_right_bracket, n)\n",
    "\n",
    "            if current_right_bracket < current_left_bracket:\n",
    "                dfs(comb+')', current_left_bracket, current_right_bracket + 1, n)\n",
    "        \n",
    "        dfs('', 0, 0, n)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        used = [0]*(2*n)\n",
    "        source = ['(']*(n) +[')']*(n)\n",
    "        reslut = []\n",
    "        def back(path,reslut,n,source,used):\n",
    "            if len(path[:]) == 2*n:\n",
    "                reslut.append(''.join(path[:]))\n",
    "                return\n",
    "            for i in range(2*n):\n",
    "                if i>=n and sum(used[:n])<=sum(used[n:]) or used[i] or not used[i-1] and source[i] == source[i-1]:\n",
    "                    continue\n",
    "                path.append(source[i])\n",
    "                used[i] = 1\n",
    "                back(path,reslut,n,source,used)\n",
    "                path.pop()\n",
    "                used[i] = 0\n",
    "        back([],reslut,n,source,used)\n",
    "        return reslut\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = []\n",
    "        def backtrack(S, left, right):\n",
    "            if len(S) == 2 * n:\n",
    "                ans.append(''.join(S))\n",
    "                return\n",
    "            if left < n:\n",
    "                S.append('(')\n",
    "                backtrack(S, left+1, right)\n",
    "                S.pop()\n",
    "            if right < left:\n",
    "                S.append(')')\n",
    "                backtrack(S, left, right+1)\n",
    "                S.pop()\n",
    "\n",
    "        backtrack([], 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        result = []\n",
    "        def foo(left, right, pre):\n",
    "            if left == 0 and right == 0:\n",
    "                result.append(pre)\n",
    "            else:\n",
    "                if left >= 1:\n",
    "                    foo(left - 1, right, pre+\"(\")\n",
    "                if left < right:\n",
    "                    foo(left, right-1, pre+\")\")\n",
    "        foo(n, n , '')\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ret = []\n",
    "        def dfs(l, r, s):\n",
    "            if l == n and r == n:\n",
    "                ret.append(s)\n",
    "            if l > n or r > n:\n",
    "                return\n",
    "            if l > r:\n",
    "                dfs(l, r+1, s + ')')\n",
    "            dfs(l+1, r, s +'(')\n",
    "\n",
    "        dfs(1, 0, '(')\n",
    "        return ret\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def generate(A):\n",
    "            if len(A) == 2*n:\n",
    "                if valid(A):\n",
    "                    ans.append(\"\".join(A))\n",
    "            else:\n",
    "                A.append('(')\n",
    "                generate(A)\n",
    "                A.pop()\n",
    "                A.append(')')\n",
    "                generate(A)\n",
    "                A.pop()\n",
    "\n",
    "        def valid(A):\n",
    "            bal = 0\n",
    "            for c in A:\n",
    "                if c == '(': bal += 1\n",
    "                else: bal -= 1\n",
    "                if bal < 0: return False\n",
    "            return bal == 0\n",
    "\n",
    "        ans = []\n",
    "        generate([])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = set()\n",
    "        def generate(temp, l, r):\n",
    "            if l == n:\n",
    "                ans.add(temp + \")\" * (n-r))\n",
    "                return\n",
    "            \n",
    "            if l > r:\n",
    "                generate(temp + \"(\", l+1, r)\n",
    "                generate(temp + \")\", l, r+1)\n",
    "            else:\n",
    "                generate(temp + \"(\", l+1, r)\n",
    "        \n",
    "        generate(\"\", 0, 0)\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = n * 2\n",
    "        ans = []\n",
    "        path = [''] * m\n",
    "        def dfs(i: int, open: int) -> None:\n",
    "            if i == m:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            if open < n:  # 可以填左括号\n",
    "                path[i] = '('\n",
    "                dfs(i + 1, open + 1)\n",
    "            if i - open < open:  # 可以填右括号\n",
    "                path[i] = ')'\n",
    "                dfs(i + 1, open)\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        def dfs(left: int, right: int, ans: List[str]) -> None:\n",
    "            if len(ans) == 2 * n:\n",
    "                ansCopy = ans[:]\n",
    "                res.append(''.join(ansCopy))\n",
    "                return\n",
    "            if left < n:\n",
    "                ans.append('(')\n",
    "                dfs(left + 1, right, ans)\n",
    "                ans.pop()\n",
    "            if right < left and right < n:\n",
    "                ans.append(')')\n",
    "                dfs(left, right + 1, ans)\n",
    "                ans.pop()\n",
    "        dfs(1,0,['('])           \n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        # print(self.isValid('()()'))\n",
    "        def backtracing(comb, res, ) -> None:\n",
    "            if len(comb) == n * 2:\n",
    "                if self.isValid(comb) == True:\n",
    "                    res.append(''.join(comb))\n",
    "                return \n",
    "            \n",
    "            for b in [')', '(']:\n",
    "                comb.append(b)\n",
    "                backtracing(comb, res)\n",
    "                comb.pop()\n",
    "\n",
    "        res = []\n",
    "        backtracing([], res)\n",
    "        return res \n",
    "    \n",
    "    def isValid(self, string: str) -> bool:\n",
    "        stack = []\n",
    "        for s in string:\n",
    "            if s == '(':\n",
    "                stack.append(')')\n",
    "            elif s == ')':\n",
    "                if stack:\n",
    "                    if s == stack[-1]:\n",
    "                        stack.pop()\n",
    "                else:\n",
    "                    return False \n",
    "        \n",
    "        if stack:\n",
    "            return False\n",
    "        else:\n",
    "            return True \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans=[]\n",
    "        def trace(s,left,right):\n",
    "            if len(s)==2*n:\n",
    "                ans.append(\"\".join(s))\n",
    "                return \n",
    "            if left < n :\n",
    "                s.append('(')\n",
    "                trace(s,left+1,right)\n",
    "                s.pop()\n",
    "            if right < left :\n",
    "                s.append(')')\n",
    "                trace(s,left,right+1)\n",
    "                s.pop()\n",
    "        trace([],0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n <= 0: return []\n",
    "        res = []\n",
    "\n",
    "        def dfs(paths, left, right):\n",
    "            if left > n or right > left: return\n",
    "            if len(paths) == n * 2:  # 因为括号都是成对出现的\n",
    "                res.append(paths)\n",
    "                return\n",
    "\n",
    "            dfs(paths + '(', left + 1, right)  # 生成一个就加一个\n",
    "            dfs(paths + ')', left, right + 1)\n",
    "\n",
    "        dfs('', 0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = n * 2\n",
    "        ans = []\n",
    "        path = [''] * m\n",
    "        def dfs(i: int, open: int) -> None:\n",
    "            if i == m:\n",
    "                ans.append(''.join(path))\n",
    "                return\n",
    "            if open < n:  # 可以填左括号\n",
    "                path[i] = '('\n",
    "                dfs(i + 1, open + 1)\n",
    "            if i - open < open:  # 可以填右括号\n",
    "                path[i] = ')'\n",
    "                dfs(i + 1, open)\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        self.n = n\n",
    "        self.res = []\n",
    "        def generates(cur, left, right):\n",
    "            if left == n and right == n:\n",
    "                self.res.append(cur)\n",
    "                return\n",
    "            \n",
    "            if left < right:\n",
    "                return\n",
    "\n",
    "            if left <n:\n",
    "                generates(cur + \"(\", left+1, right)\n",
    "            if right <n:\n",
    "                generates(cur + \")\", left, right +1)\n",
    "        \n",
    "        generates(\"\", 0, 0)\n",
    "\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        # print(self.isValid('()()'))\n",
    "        def backtracing(comb, res, ) -> None:\n",
    "            if len(comb) == n * 2:\n",
    "                if self.isValid(comb) == True:\n",
    "                    res.append(''.join(comb))\n",
    "                return \n",
    "            \n",
    "            for b in [')', '(']:\n",
    "                comb.append(b)\n",
    "                backtracing(comb, res)\n",
    "                comb.pop()\n",
    "\n",
    "        res = []\n",
    "        backtracing([], res)\n",
    "        return res \n",
    "    \n",
    "    def isValid(self, string: str) -> bool:\n",
    "        stack = []\n",
    "        for s in string:\n",
    "            if s == '(':\n",
    "                stack.append(')')\n",
    "            elif s == ')':\n",
    "                if stack:\n",
    "                    if s == stack[-1]:\n",
    "                        stack.pop()\n",
    "                else:\n",
    "                    return False \n",
    "        \n",
    "        if stack:\n",
    "            return False\n",
    "        else:\n",
    "            return True \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = n*2\n",
    "        path = [\" \"]*m\n",
    "        ans = []\n",
    "        def dfs(length, open):\n",
    "            if length == m:\n",
    "                ans.append(\"\".join(path))\n",
    "                return\n",
    "            if open < n:\n",
    "                path[length] = \"(\"\n",
    "                dfs(length+1, open+1)\n",
    "            if length-open <open:\n",
    "                path[length] = \")\"\n",
    "                dfs(length+1, open)\n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        path = deque()\n",
    "\n",
    "        def check(string):\n",
    "            stk = deque()\n",
    "            for c in string:\n",
    "                if c == '(':\n",
    "                    stk.append(')')\n",
    "                elif c == ')':\n",
    "                    if len(stk) == 0 or c != stk.pop():\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        # left, right: 当前可用的括号数目\n",
    "        def dfs(left, right):\n",
    "            if len(path) == 2*n:\n",
    "                # 合法性\n",
    "                if check(path):\n",
    "                    res.append(\"\".join(path))\n",
    "                return\n",
    "            if left > 0:\n",
    "                path.append('(')\n",
    "                dfs(left-1, right)\n",
    "                path.pop()\n",
    "            if right > 0:\n",
    "                path.append(')')\n",
    "                dfs(left, right-1)\n",
    "                path.pop()\n",
    "        \n",
    "        dfs(n, n)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = n * 2\n",
    "        if n<=0:\n",
    "            return\n",
    "        res = []\n",
    "        def dfs(path,l,r):\n",
    "            if l > n or r > l:\n",
    "                return\n",
    "            if len(path) == m:\n",
    "                res.append(path)\n",
    "                return \n",
    "            dfs(path + '(',l+1,r)\n",
    "            dfs(path + ')',l,r+1)\n",
    "        \n",
    "        dfs('',0,0)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def dfs(acc, path, res, score):\n",
    "            if not acc:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i in range(len(acc)):\n",
    "                if acc[i]==')' and score==0:\n",
    "                    continue\n",
    "                if i>0 and acc[i]==acc[i-1]:continue\n",
    "                tmp = acc[:i]+acc[i+1:]\n",
    "                dfs(tmp,path+acc[i],res,score+1 if acc[i]=='(' else score-1)\n",
    "        res = []\n",
    "        dfs('('*n+')'*n,'',res,0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        res =[]\n",
    "        def f(l,r,s):\n",
    "            if l==r==n:\n",
    "                res.append(s)\n",
    "            if l<n: \n",
    "                f(l+1,r,s+'(')\n",
    "            if r<l :\n",
    "                f(l,r+1,s+')')\n",
    "        f(0,0,'')\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def dfs(acc, path, res, score):\n",
    "            if not acc:\n",
    "                res.append(path)\n",
    "                return\n",
    "            for i in range(len(acc)):\n",
    "                if acc[i]==')' and score==0:\n",
    "                    continue\n",
    "                if i>0 and acc[i]==acc[i-1]:continue\n",
    "                tmp = acc[:i]+acc[i+1:]\n",
    "                dfs(tmp,path+acc[i],res,score+1 if acc[i]=='(' else score-1)\n",
    "        res = []\n",
    "        dfs('('*n+')'*n,'',res,0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n <= 0: return []\n",
    "        res = []\n",
    "\n",
    "        def dfs(paths, left, right):\n",
    "            if left > n or right > left: return\n",
    "            if len(paths) == n * 2:  # 因为括号都是成对出现的\n",
    "                res.append(paths)\n",
    "                return\n",
    "\n",
    "            dfs(paths + '(', left + 1, right)  # 生成一个就加一个\n",
    "            dfs(paths + ')', left, right + 1)\n",
    "\n",
    "        dfs('', 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        path = [\"\"] * (2*n)\n",
    "        ans = []\n",
    "        def dfs(i,left):\n",
    "            if i == n * 2:\n",
    "                ans.append(\"\".join(path))\n",
    "                return\n",
    "            if left < n:\n",
    "                path[i] = \"(\"\n",
    "                dfs(i+1,left+1)\n",
    "            if i - left < left:\n",
    "                path[i] = \")\"\n",
    "                dfs(i+1,left)\n",
    "        dfs(0,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        res = []\n",
    "        def generateResult(tuple_res):\n",
    "            str, left, right = tuple_res\n",
    "            str_dict = {0:(f\"{str}(\", left + 1, right),\n",
    "                        1:(f\"{str})\", left, right + 1)}\n",
    "            if left == right and left == n:\n",
    "                res.append(str)\n",
    "                return\n",
    "            if left == right:\n",
    "                param1 = str_dict[0]\n",
    "                generateResult(param1)\n",
    "            elif left == n:\n",
    "                param2 = str_dict[1]\n",
    "                generateResult(param2)\n",
    "            else:\n",
    "                for i in range(2):\n",
    "                    param = str_dict[i]\n",
    "                    generateResult(param)\n",
    "                \n",
    "        generateResult((\"\", 0, 0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        m = n * 2\n",
    "        ans = []\n",
    "        store = ['']*m\n",
    "        # 定义左括号的个数为open，右括号个数为i-open\n",
    "        # dfs判断i的位置选择左括号还是右括号\n",
    "        def dfs(i, open):\n",
    "            if i == m:\n",
    "                ans.append(''.join(store))\n",
    "                return\n",
    "            if open < n:\n",
    "                store[i] = '('\n",
    "                dfs(i+1, open+1)\n",
    "            if i-open < open:\n",
    "                store[i] = ')'\n",
    "                dfs(i+1, open)\n",
    "        dfs(0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        #暴力\n",
    "        def generate(A):\n",
    "            if len(A) == 2*n:\n",
    "                if valid(A):\n",
    "                    ans.append(\"\".join(A))\n",
    "            else:\n",
    "                    A.append('(')\n",
    "                    generate(A)\n",
    "                    A.pop()\n",
    "                    A.append(')')\n",
    "                    generate(A)\n",
    "                    A.pop()\n",
    "        \n",
    "        def valid(A):\n",
    "            bal = 0\n",
    "            for c in A:\n",
    "                if c=='(':\n",
    "                    bal+=1\n",
    "                else:\n",
    "                    bal-=1\n",
    "            \n",
    "                if bal < 0:\n",
    "                    return False\n",
    "\n",
    "            return bal==0\n",
    "\n",
    "        ans=[]\n",
    "        generate([])\n",
    "        \n",
    "        return ans                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        dp = defaultdict(list)\n",
    "        dp[1] = [\"()\"]\n",
    "        for i in range(2, n+1):\n",
    "            result = set()\n",
    "            for j in range(1, i):\n",
    "                for item1 in dp[j]:\n",
    "                    for item2 in dp[i-j]:\n",
    "                        result.add(item1+item2)\n",
    "                    if j == i-1:\n",
    "                        result.add(\"(\"+item1+\")\")\n",
    "            dp[i] = list(result)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        dp = [[''],[\"()\"]]\n",
    "        #i为多出了多少个括号\n",
    "        for i in range(1,n+1):\n",
    "            #j为左边被括的括号数量，i-j为右边没被括的括号数量\n",
    "            temp_list = []\n",
    "            for j in range(i+1):\n",
    "                for a in dp[j]:\n",
    "                    for b in dp[i-j]:\n",
    "                        temp_str = '(' + a + ')' + b\n",
    "                        temp_list.append(temp_str)\n",
    "            dp.append(temp_list)\n",
    "\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def backtrack(s='', left=0, right=0):\n",
    "            if len(s) == 2 * n:\n",
    "                res.append(s)\n",
    "                return\n",
    "            if left < n:\n",
    "                backtrack(s + '(', left + 1, right)\n",
    "            if right < left:\n",
    "                backtrack(s + ')', left, right + 1)\n",
    "\n",
    "        res = []\n",
    "        backtrack()\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        return self.generate(n, n)\n",
    "\n",
    "    def generate(self, left: int, right: int) -> List[str]:\n",
    "        if right == 0:\n",
    "            return []\n",
    "        if left == 0:\n",
    "            return [\")\" * right]\n",
    "        result = []\n",
    "        temp = self.generate(left - 1, right)\n",
    "        for s in temp:\n",
    "            result.append(\"(\" + s)\n",
    "        if right - 1 >= left:\n",
    "            temp = self.generate(left, right - 1)\n",
    "            for s in temp:\n",
    "                result.append(\")\" + s)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "\n",
    "        def dfs(prefix, i, j):\n",
    "            if not i and not j:\n",
    "                res.append(''.join(prefix))\n",
    "                return \n",
    "            if i>0:\n",
    "                prefix.append('(')\n",
    "                dfs(prefix, i-1, j)\n",
    "                prefix.pop(-1)\n",
    "            if j>i:\n",
    "                prefix.append(')')\n",
    "                dfs(prefix, i, j-1)\n",
    "                prefix.pop(-1)\n",
    "        res = []\n",
    "        dfs([], n, n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        n_left, n_right = n, n\n",
    "        res = []\n",
    "        tmp = []\n",
    "        def dfs(n_left, n_right):\n",
    "            if n_left == 0 and n_right == 0:\n",
    "                res.append(\"\".join(tmp))\n",
    "                return\n",
    "\n",
    "            if n_left < n_right:\n",
    "                if n_left > 0:\n",
    "                    tmp.append(\"(\")\n",
    "                    dfs(n_left - 1, n_right)\n",
    "                    tmp.pop()\n",
    "                tmp.append(\")\")\n",
    "                dfs(n_left, n_right-1)\n",
    "                tmp.pop()\n",
    "            elif n_left == n_right:\n",
    "                    tmp.append(\"(\")\n",
    "                    dfs(n_left - 1, n_right)\n",
    "                    tmp.pop()\n",
    "\n",
    "        dfs(n_left, n_right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        ans = ['()']\n",
    "\n",
    "        for i in range(1, n):\n",
    "            cur = set()\n",
    "            for item in ans:\n",
    "                for k in range(len(item)):\n",
    "                    cur.add(item[:k]+'()'+item[k:])\n",
    "            ans = list(cur)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        dp = [[''],[\"()\"]]\n",
    "        #i为多出了多少个括号\n",
    "        for i in range(1,n+1):\n",
    "            #j为左边被括的括号数量，i-j为右边没被括的括号数量\n",
    "            temp_list = []\n",
    "            for j in range(i+1):\n",
    "                for a in dp[j]:\n",
    "                    for b in dp[i-j]:\n",
    "                        temp_str = '(' + a + ')' + b\n",
    "                        temp_list.append(temp_str)\n",
    "            dp.append(temp_list)\n",
    "\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        if n == 0:\n",
    "            return [\"\"]\n",
    "        if n == 1:\n",
    "            return [\"()\"]\n",
    "        else:\n",
    "            rs = []\n",
    "            for i in range(0, n):\n",
    "                for x in self.generateParenthesis(i):\n",
    "                    for y in self.generateParenthesis(n-1-i):\n",
    "                        rs.append(f\"({x}){y}\")\n",
    "                        rs.append(f\"{x}({y})\")\n",
    "            return list(set(rs))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        def now(l,n):\n",
    "            if n==0:\n",
    "                print(l.count('('),l.count(')'))\n",
    "                if l.count('(')!=l.count(')'):\n",
    "                    res.append(l+(l.count('(')-l.count(')'))*')') \n",
    "                return \n",
    "            if n<0:\n",
    "                return  \n",
    "            if l.count('(')*2>len(l):\n",
    "                now(l+'(',n-1)\n",
    "                now(l+')',n)  \n",
    "            else:\n",
    "                now(l+'(',n-1)\n",
    "        res=[]\n",
    "        now('',n)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        data = [\"(\", \")\"]\n",
    "        re = []\n",
    "        def get_parenthesis(tmp):\n",
    "            if tmp.count(\"(\") > n or tmp.count(\")\") >n:\n",
    "                return\n",
    "            if len(tmp) == 2*n and valid(tmp):\n",
    "                re.append(tmp)\n",
    "                return\n",
    "            if len(tmp) > 2*n:\n",
    "                return\n",
    "            for i in range(0, len(data)):\n",
    "                get_parenthesis(tmp + [data[i]])\n",
    "\n",
    "        def valid(parenthesis):\n",
    "            left = 0\n",
    "            for i in range(0, len(parenthesis)):\n",
    "                if parenthesis[i] == \"(\":\n",
    "                    left += 1\n",
    "                if parenthesis[i] == \")\" :\n",
    "                    if left > 0:\n",
    "                        left -= 1\n",
    "                    else:\n",
    "                        return False\n",
    "            if left == 0:\n",
    "                return True\n",
    "                \n",
    "        for i in range(0, len(data)):\n",
    "                get_parenthesis([] + [data[i]])\n",
    "        res = []\n",
    "        for ele in re:\n",
    "            res.append(\"\".join(ele))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        res = [[[] for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            dp[0][i] = dp[0][i - 1] + 1\n",
    "            dp[i][0] = dp[i - 1][0] - 1\n",
    "            res[0][i].append('(' * i)\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = dp[i - 1][j] - 1\n",
    "                if dp[i - 1][j] > 0:\n",
    "                    for s in res[i - 1][j]:\n",
    "                        res[i][j].append(s + ')')\n",
    "                if dp[i][j - 1] > -1:\n",
    "                    for s in res[i][j - 1]:\n",
    "                        res[i][j].append(s + '(')\n",
    "\n",
    "        return res[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def generateParenthesis(self, n: int) -> List[str]:\n",
    "        dp = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        res = [[[] for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            dp[0][i] = dp[0][i - 1] + 1\n",
    "            dp[i][0] = dp[i - 1][0] - 1\n",
    "            res[0][i].append('(' * i)\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = dp[i - 1][j] - 1\n",
    "                if dp[i - 1][j] > 0:\n",
    "                    for s in res[i - 1][j]:\n",
    "                        res[i][j].append(s + ')')\n",
    "                if dp[i][j - 1] > -1:\n",
    "                    for s in res[i][j - 1]:\n",
    "                        res[i][j].append(s + '(')\n",
    "\n",
    "        return res[-1][-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
